#include <iostream>
#include <fstream>
#include "SortingConfig.h"

using namespace std;

void swap(int &a, int &b) {
    int t=a;
    a = b;
    b = t;
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int _val): val(_val), next(nullptr){};
};


ListNode* merge_sort(ListNode *list) {
    // 如果输入list为空，或则只有一个元素则直接返回
    if (!list || !list->next) return list;

    int step=1, n=0;
    ListNode *start=list, *left, *right;
    ListNode *head, *tail, *t;
    // 计算链表长度
    t = list;
    while(t) {
        n ++;
        t = t->next;
    }
    // 链表归并排序
    int cl, cr;
    head = tail = nullptr;
    while (step < n) {
        // 设置两个链表头
        left=right=start;
        for(int i=0; i<step && right; ++i) {
            right = right->next;
        }
        cl = cr = 0;
        while (left && cl < step || right && cr < step) {
            if ((left && cl < step) && (right && cr < step)) {
                if (left->val < right->val) {
                    t = left;
                    left = left->next;
                    cl ++;
                } else {
                    t = right;
                    right = right->next;
                    cr ++;
                }
            } 
            else if (left && cl < step) {
                t = left;
                left = left->next;
                cl ++;
            } 
            else {
                t = right;
                right = right->next;
                cr ++;
            }
            if (!tail) {
                head = tail = t;
            } else {
                tail->next = t;
                tail = t;
            }
            tail->next = nullptr;
        }
        if (right) {
            start = right;
        } 
        else {
            start = head;
            step *= 2;
            head = tail = nullptr;
        }
    }
    return start;
}


void bucket_sort(int *arr, int n) {
    // 桶排序算法
    int bucketSize = 10;
    ListNode *buckets[bucketSize] = {nullptr};
    ListNode *tails[bucketSize] = {nullptr};
    ListNode *t;
    // 计算数组的最大、最小值
    int minNum=INT32_MAX, maxNum=INT32_MIN;
    for(int i=0; i<n; ++i) {
        if (arr[i] < minNum) minNum = arr[i];
        if (arr[i] > maxNum) maxNum = arr[i];
    }
    int step = (maxNum - minNum) / bucketSize + 1;
    // 将数据依次放入桶中
    for (int i=0; i<n; ++i) {
        int b = (arr[i] - minNum)/step;
        if (!tails[b]) {
            buckets[b] = tails[b] = new ListNode(arr[i]);
        } else {
            tails[b]->next = new ListNode(arr[i]);
            tails[b] = tails[b]->next;
        }
    }

    for (int i=0, p=0; i<bucketSize; ++i) {
        // 对桶中数据进行排序
        buckets[i] = merge_sort(buckets[i]);
        ListNode *tt=buckets[i];
        
        // 将排序后桶中数据依次放入待排序数组中
        while(buckets[i]) {
            t = buckets[i];
            arr[p] = t->val;
            ++p;
            buckets[i] = t->next;
            delete t;
        }
    }
}

int main(int argc, char *argv[]) {
    cout << "Sorting Version: " << Sorting_VERSION_MAJOR 
         << "." << Sorting_VERSION_MINOR<<endl;
    // 参数解析
    ifstream input;
    if (argc > 1) {
        input.open(argv[1], ios::in);
    }

    int n;
    if (argc > 1) input >> n;
    else cin >> n;
    int arr[n];
    if (argc > 1){
        for(int i=0; i<n;++i) input >> arr[i];
        input.close();
    } else {
        for(int i=0; i<n;++i) cin >> arr[i];
    }
    // 排序
    bucket_sort(arr, n);
    // 打印结果
    for(int i=0; i<n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}